package com.zp.self.module.level_4_算法练习.算法.双指针.快慢指针;

import com.zp.self.module.level_4_算法练习.数据结构.链表.ListNode;

/**
 * @author By ZengPeng
 */
public class 力扣_19_删除链表的倒数第N个结点 {
    //测试
    public static void main(String[] args) {
        ListNode node = ListNode.getNode();
        ListNode listNode = new 力扣_19_删除链表的倒数第N个结点().removeNthFromEnd(node, 2);
        while (listNode!=null){
            System.out.println(listNode.val+",");
            listNode = listNode.next;
        }

    }

    /**
    题目：给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

     示例 1：
     输入：head = [1,2,3,4,5], n = 2
     输出：[1,2,3,5]

     示例 2：
     输入：head = [1], n = 1
     输出：[]

     示例 3：
     输入：head = [1,2], n = 1
     输出：[1]

    分析：【perfect】
       1.遍历一次，通过list记录每个节点的位置，再通过下标找到要删除的位置
        递归，这个其实也相当于创建了数组存储递归栈   -- 并不很优秀，且不能转while
        大神解法【快慢指针】: -- 我开始也想到了，但是不好实现【因为是后面的节点: 让快指针先走n步】
                                特殊情况  ，头部节点

    边界值 & 注意点：
       1.头节点、尾节点
       2.只有一个节点
     **/
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // 大神解法:快慢指针
        ListNode s=head,f=head;
        for (int i = 0; i < n; i++)
            f=f.next;
        if(f==null)return head.next;
        while (f.next!=null){
            s= s.next;
            f = f.next;
        }
        s.next=s.next.next;
        return head;

        //1.遍历一次，通过list记录每个节点的位置
        /*List<ListNode> list = new ArrayList<>();
        ListNode node = head;
        while (node!=null){
            list.add(node);
            node = node.next;
        }
        if(n==list.size())return head.next;  //头部
        if(n!=1) node = list.get(list.size()-n + 1); //非尾部
        list.get(list.size()-n - 1).next = node;
        return head;*/
    }
}
